from typing import List


class Solution:
    def maxSumOfThreeSubarrays(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        windows = [0 for _ in range(n - k + 1)]
        for i in range(k):
            windows[0] += nums[i]
        for i in range(1, n - k + 1):
            windows[i] = windows[i - 1] - nums[i - 1] + nums[i + k - 1]

        prefix = [0 for _ in range(n)]  # 0 ~ i 位置 最大以何开头
        maxWindow = windows[0]
        maxIndex = 0
        for i in range(n - k + 1):
            if windows[i] > maxWindow:
                maxWindow = windows[i]
                maxIndex = i
            prefix[i] = maxIndex

        maxWindow = windows[-1]
        maxIndex = n - k
        suffix = [0] * n
        for i in range(n - k, -1, -1):
            if windows[i] > maxWindow:
                maxWindow = windows[i]
                maxIndex = i
            suffix[i] = maxIndex

        maxAns = -float('inf')
        for i in range(k, n - k):
            index1 = prefix[i]
            index2 = suffix[i + k]
            ans = windows[i] + windows[index1] + windows[index2]
            if ans > maxAns:
                maxAns = ans
                l = index1, i, index2
        return l


if __name__ == '__main__':
    s = Solution()
    r = s.maxSumOfThreeSubarrays(nums=[1, 2, 1, 2, 6, 7, 5, 1], k=2)
    print(r)
